<?php
/**
 * @title 1545. 找出第 N 个二进制字符串中的第 K 位 - 数学
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return String
     */
    function findKthBit($n, $k) {
        /**
         * @since 2021-09-06 是否取反
         */
        $not = false;

        /**
         * @since 2021-09-06 找字符串第K位
         */
        while($n > 1){
            /**
             * @since 2021-09-06 长度
             */
            $len = pow(2, $n) - 1;

            /**
             * @since 2021-09-06 中间键值
             */
            $mid = (($len+1) >> 1) - 1;
            // echo "len={$len}, mid={$mid}, k={$k}", PHP_EOL;

            /**
             * @since 2021-09-06 是否中间键值
             */
            if($k-1 == $mid){
                if($not){
                    return "0";
                } else {
                    return "1";
                }
            } elseif($k-1 < $mid) {
                /**
                 * @since 2021-09-06 前半段
                 */
            } else {
                /**
                 * @since 2021-09-06 后半段
                 */
                $k = $len - $k + 1;
                $not = !$not;
            }

            /**
             * @since 2021-09-06 下次
             */
            $n--;
        }

        /**
         * @since 2021-09-06 收官
         */
        if($not){
            return "1";
        } else {
            return "0";
        }
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.11_9.php
 */
$datas = [
    [3,1], // 0
    [4,11], // 1
    [1,1], // 0
    [2,3], // 1
    // [3,5],
    // [2,1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->findKthBit($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
